//
// Created by liweimin on 2021/7/1.
//

#ifndef DATA_STRUCTURE_MAZE_H
#define DATA_STRUCTURE_MAZE_H

#endif //DATA_STRUCTURE_MAZE_H

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//定义方向
#define UP 2 //上
#define DOWN 1//下
#define LEFT 3//左
#define RIGHT 4//右


#define STACK_INIT_SIZE 100//栈大小
#define STACK_INCREMENT 10//栈增量

typedef struct //迷宫位置
{
    int x;//横坐标
    int y;//纵坐标
} Position;

/**
 * 栈元素
 */
typedef struct
{
    int ord;//序号
    Position seat;//位置
    int dir;//方向
} Element;

/**
 * 栈
 */
typedef struct
{
    Element *base;//栈底指针-->顺序栈中保持不动指向底部
    Element *top;//栈顶指针
    int stack_size;
} MazeStack;

/**
 * 初始化栈
 * @param mazeStack
 * @return
 */
bool init(MazeStack *mazeStack)
{
    mazeStack->base = (Element *) malloc(STACK_INIT_SIZE * sizeof(Element));
    if (!mazeStack->base)
    {
        printf("内存分配失败!初始化失败！\n");
        return false;
    }
    mazeStack->top = mazeStack->base;
    mazeStack->stack_size = STACK_INIT_SIZE;
    return true;
}

/**
 * 判空
 */
bool isEmpty(MazeStack *stack)
{
    return (stack->base == stack->top);
}

/**
 * 遍历栈
 * @param mazeStack
 */
void traverse(MazeStack *mazeStack)
{
    if (isEmpty(mazeStack))
    {
        printf("空栈！\n");
        return;
    }
    Element *ptr = mazeStack->top - 1;
    while (mazeStack->base <= ptr)
    {
        printf("(%d,%d) 方向：%d\n", ptr->seat.x, ptr->seat.y, ptr->dir);
        ptr--;
    }
}

/**
 * 入栈
 * @param mazeStack
 * @param element
 */
void push(MazeStack *mazeStack, Element element)
{
    *mazeStack->top++ = element;
}

/**
 * 出栈
 * @param mazeStack
 * @param e
 */
void pop(MazeStack *mazeStack, Element *e)
{
    if (isEmpty(mazeStack))
    {
        return;
    }
    *e = *(--mazeStack->top);
}